/*
两个已经升序排列的单链表的合并
归并两个升序单链表
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "link.h"

void init(Link *plink)
{
    plink->head = (Node *)malloc(sizeof(Node));
    plink->head->next = NULL;
    plink->size = 0;
}

bool is_empty(Link *plink)
{
    return plink->head == NULL;
}

Node *find(Link *plink, int index)
{
    if (is_empty(plink) || index < 1)
    {
        printf("您输入的链表为空或者您输入的索引非法\n");
        return NULL;
    }
    Node *temp = plink->head;
    // temp=plink->head;
    int i = 1;
    while (temp != NULL && i < index)
    {
        i++;
        temp = temp->next;
    }
    return temp;
}

int insert(Link *plink, ElementType element, int index)
{
    Node *n = (Node *)malloc(sizeof(Node));
    Node *t = find(plink, index);
    memcpy(&n->data, &element, sizeof(ElementType));
    // n->next=NULL;
    n->next = t->next;
    t->next = n;
}

void add(Link *plink, ElementType element)
{
    if (is_empty(plink))
        return;
    Node *n = (Node *)malloc(sizeof(Node));
    memcpy(&n->data, &element, sizeof(ElementType));
    Node *t = plink->head;
    while (t->next != NULL)
        t = t->next;
    t->next = n;
    n->next = NULL;
}

int delete_link(Link *plink, int index)
{
    Node *t = find(plink, index);

    Node *n1 = t->next;
    t->next = n1->next;
    free(n1);
    n1->next = NULL;
}

void make_empty(Link *plink)
{
    Node *temp = plink->head;
    while (temp != NULL)
    {
        Node *n = temp->next;
        free(temp);
        temp->next = NULL;
        temp = n;
    }
}

int LengthList(Link *plink)
{
    int len = 0;
    Node *t = plink->head->next;
    while (t != NULL)
    {
        len++;
        t = t->next;
    }
    return len;
}

void display(Link *plink)
{
    Node *t = plink->head->next;
    while (t != NULL)
    {
        printf("%d,", t->data);
        t = t->next;
    }
    putchar('\n');
}

int MergeList(Link *la, Link *lb, Link *lc)
{
    if (is_empty(la) || is_empty(lb))
    {
        printf("您输入的链表a和b是空链表\n");
        return 0;
    }

    Node *n1 = la->head->next;
    Node *n2 = lb->head->next;
    Node *n3 = lc->head;
    Node *pp;
    // printf("sss\n");
    while (n2 != NULL && n1 != NULL)
    {
        if (n1->data < n2->data)
        {
            pp = n1;
            // printf("%p\n",pp);
            n1 = n1->next;
        }
        else
        {
            pp = n2;
            n2 = n2->next;
        }
        n3->next = (Node *)malloc(sizeof(Node));
        n3 = n3->next;
        n3->data = pp->data;
        n3->next = NULL;
    }
    while (n2 != NULL)
    {
        n3->next = (Node *)malloc(sizeof(Node));
        n3 = n3->next;
        n3->data = n2->data;
        n3->next = NULL;
        n2 = n2->next;
    }
    while (n1 != NULL)
    {
        n3->next = (Node *)malloc(sizeof(Node));
        n3 = n3->next;
        n3->data = n1->data;
        n3->next = NULL;
        n2 = n1->next;
    }
    return 1;
}

int RverseList(Node *pp)
{
    if (pp == NULL)
        return 0;
    Node *ss = pp->next; // pp之后的节点
    Node *ssnext;
    pp->next = NULL; // 从pp处断开
    while (ss != NULL)
    {
        ssnext = ss->next;
        // 以下两行代码就相当于再pp后面插入ss
        ss->next = pp->next;
        pp->next = ss;
        ss = ssnext;
    }
    return 1;
}

Node *FindKNode(Link *LL, unsigned int kk)
{
    Node *temp = LL->head->next;
    Node *n = LL->head->next;
    int i = 1;
    // 先让temp跑kk个节点
    while (i < kk && temp != NULL)
    {
        temp = temp->next;
        i++;
    }

    if (temp == NULL)
        return NULL;
    // 让temp继续跑到尾，n也开始跑
    while (1)
    {
        temp = temp->next;
        if (temp == NULL)
            break;
        n = n->next;
    }
    // 这时得到的就是倒数的第kk个节点
    return n;
}

void PrintfNode(Node *pp)
{
    if (pp == NULL)
        return;
    else
        PrintfNode(pp->next);
    printf("%d,", pp->data);
    return;
}

Node *FindLoop(Link *LL)
{
    Node *fast = LL->head;
    Node *slow = LL->head;

    while (slow != NULL && fast != NULL)
    {
        slow = slow->next;
        fast = fast->next->next; // 快指针走两步
        if (slow == fast)
            break;
    }
    if (fast == NULL || fast->next == NULL)
        return NULL; // 没有环

    Node *p1 = LL->head;
    Node *p2 = slow;
    while (1)
    {
        if (p1 == p2)
            break;
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

// 找出两个汇聚单链表的公共结点，如果没有汇聚，返回空，如果有，返回汇聚的第一个结点。
Node *FindJoin(Link *La, Link *Lb)
{
    int len1 = LengthList(La);
    int len2 = LengthList(Lb);

    Node *ta, *tb;
    // 若链表la长于lb，则La先跑到len1-len2处;
    for (ta = La->head->next; len2 < len1; len1--)
    {
        ta = ta->next;
    }

    // 若链表lb长于la，则Lb先跑到len2-len1处;
    for (tb = Lb->head->next; len1 < len2; len2--)
    {
        tb = ta->next;
    }

    while (1)
    {
        if (ta == tb)
            break;
        ta = ta->next;
        tb = tb->next;
        if (ta == NULL)
            return NULL;
    }
    return ta;
}

// 假设线性表L=(a1,a2,a3,...,an-2,an-1,an)采用带头结点的单链表保存，数据结点的个数为偶数。
// 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点。
// 最后得到线性表L=(a1,an,a2,an-1,a3,an-2,...)。
// 这里要对链表的表长为奇偶分开处理
void ReplaceList(Link *LL)
{
    int len = LengthList(LL);

    // 第1步：找到链表的中间结点。
    Node *fast = LL->head, *slow = LL->head; // 设置快慢指针。

    if (len % 2 == 0)
    {
        while (fast->next != NULL)
        {
            // 慢指针走一步，快指针走两步。
            slow = slow->next;
            fast = fast->next->next; // 因为数据结点的个数为偶数，所以这里不会出现操作空指针的情况。
            // printf("slow=%p,data=%d\n",slow,slow->data);
            // printf("fast=%p,data=%d\n",fast,fast->data);
        }
    }
    else
    {
        while (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next->next; // 因为数据结点的个数为奇数，所以这里不会出现操作空指针的情况。
        }
    }
    // slow指向链表前半段最后一个结点。
    // printf("slow=%p,data=%d\n",slow,slow->data);

    // 第2步：把链表的后半段原地逆置。
    //   printf("aaaa\n");
    RverseList(slow);
    //   printf("abba\n");

    // PrintList(LL);

    // 第3步：把链表的后半段插入到前半段中。
    Node *n1 = LL->head->next; // n1为前半段第一个数据结点。
    Node *n2 = slow->next;     // n2为后半段第一个数据结点。

    slow->next = NULL; // 链表结束标志。

    Node *tmp = NULL;

    while (n2 != NULL)
    {
        tmp = n2->next; // 保存下一结点的地址。
        n2->next = n1->next;
        n1->next = n2;
        n2 = tmp;
        n1 = n1->next->next; // n1跳到下一个插入位置。
    }
}